package linkedList;

import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 合并K个升序链表23.java
 * @Description TODO https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @createTime 2021年03月09日 19:51:00
 */
public class 合并K个升序链表23 extends BaseLinkedListTest {
    public static void main(String[] args) {
        mergeKLists(new ListNode[]{
                createLinkedList(),
                createLinkedList(1, 4, 5),
                createLinkedList(1, 3, 4),
                createLinkedList()
        });
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        //分治的方式进行
        return mergeSort(lists, 0, lists.length - 1);
    }

    private static ListNode mergeSort(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start > end) {
            return null;
        }
        int mid = (end + start) / 2;
        return mergeTwoList(mergeSort(lists, start, mid), mergeSort(lists, mid + 1, end));
    }

    private static ListNode mergeTwoList(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val > list2.val) {
            ListNode node = mergeTwoList(list1, list2.next);
            list2.next = node;
            return list2;
        } else {
            list1.next = mergeTwoList(list1.next, list2);
            return list1;
        }
    }


}
